1801G - A task for substrings - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int in(){
	int x;
	scanf("%d",&x);
	return x;
}
const int M=5e6+5,N=1e6+5;
struct ACAM{
	int ch[N][26],fa[N],len[N],val[N],tot;
	int pos[N];
	vector<int> e[N];
	int dfn[N],dfn1[N];
	int f[20][N];
	void insert(char *s){
		int p=0;
		for(int i=1;s[i];i++){
			int c=s[i]-'a';
			if(!ch[p][c])ch[p][c]=++tot,len[tot]=i;
			p=ch[p][c];pos[i]=p;
		}
		val[p]++;
	}
	int tot1;
	void dfs(int x){
		if(x)dfn[x]=++tot1;
		for(int y:e[x])dfs(y);
		dfn1[x]=tot1;
	}
	void build(){
		queue<int> q;
		for(int i=0;i<26;i++)if(ch[0][i])q.push(ch[0][i]);
		while(q.size()){
			int x=q.front();q.pop();val[x]+=val[fa[x]];
			for(int i=0;i<26;i++){
				if(ch[x][i])fa[ch[x][i]]=ch[fa[x]][i],q.push(ch[x][i]);
				else ch[x][i]=ch[fa[x]][i];
			}
		}
		for(int i=1;i<=tot;i++)e[fa[i]].push_back(i);
		dfs(0);
	}
	void init(){
		for(int i=1;i<=tot;i++)f[0][i]=fa[i];
		for(int i=1;i<20;i++)
			for(int j=1;j<=tot;j++)
				f[i][j]=f[i-1][f[i-1][j]];
	}
	void up(int &x,int d){
		if(len[x]<=d)return;
		for(int i=19;i>=0;i--)
			if(len[f[i][x]]>d)x=f[i][x];
		x=f[0][x];
	}
}T1,T2;
int n,m;
char s[M],t[N];
int p1[M],p2[M];
vector<pair<int,int> > V,ask[N];
vector<int> op[N];
ll pre[M],ans[N];
int bit[N];
void add(int p,int v){
	for(int i=p;i<N;i+=i&-i)bit[i]+=v;
}
int get(int p){
	int s=0;
	for(int i=p;i;i&=i-1)s+=bit[i];
	return s;
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	while(n--){
		scanf("%s",t+1);
		int l=strlen(t+1);
		T1.insert(t);
		for(int i=1;i<=l;i++)p1[i]=T1.pos[i];
		reverse(t+1,t+l+1);
		T2.insert(t);
		for(int i=1;i<=l;i++)p2[i]=T2.pos[i];
		for(int i=1;i<l;i++)V.emplace_back(p1[i],p2[l-i]);
	}
	T1.build(),T2.build();
	for(auto p:V){
		int x=p.first,y=p.second;
		op[T1.dfn[x]].push_back(T2.dfn[y]);
		op[T1.dfn[x]].push_back(-(T2.dfn1[y]+1));
		op[T1.dfn1[x]+1].push_back(-T2.dfn[y]);
		op[T1.dfn1[x]+1].push_back(T2.dfn1[y]+1);
	}
	int p=0;int l=strlen(s+1);
	for(int i=1;i<=l;i++){
		p=T1.ch[p][s[i]-'a'];
		pre[i]=pre[i-1]+T1.val[p];
		p1[i]=p;
	}
	p=0;
	for(int i=l;i>=1;i--){
		p=T2.ch[p][s[i]-'a'];
		p2[i]=p;
	}
	T2.init();
	for(int i=1;i<=m;i++){
		int l=in(),r=in();ans[i]=pre[r]-pre[l-1];
		int x=p1[l-1],y=p2[l];
		T2.up(y,r-l+1);
		ask[T1.dfn[x]].push_back(make_pair(T2.dfn[y],i));
	}
	for(int i=1;i<=T1.tot;i++){
		for(int j:op[i])add(abs(j),j<0?-1:1);
		for(auto p:ask[i])ans[p.second]-=get(p.first);
	}
	for(int i=1;i<=m;i++)printf("%lld ",ans[i]);puts("");
	return 0;
}